#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include "strmap.h"

//Wrapper para alocação de memória. Termina o programa e
//exibe mensagem de erro caso a alocação não tenha sido feita com sucesso.
void* allocate(int bytes);

//Chamada para verificar se uma função MPI retornou com sucesso. Exibe mensagem
//de erro e termina o programa caso contrário.
void check_status(int status);

//Verifica se a palavra é palíndromo.
int palindromo(char* palavra);

//Retorna a soma dos códigos ASCII de cada letra da palavra.
int word_to_ascii(char* palavra);

//Algoritmo do crivo de Erastótenes, adaptado para execução paralela. Retorna
//o resultado parcial do crivo no vetor primos. Executa o algoritmo em uma seção
//do intervalo determinado por max_primo, dependente do rank do processo em
//comparação com o número total de processos.
void erastotenes(int** primos, int max_primo, int rank, int slaves);

//Busca binária (utilizada na verificação de se um número é primo)
int busca_binaria(int* vetor, int tamanho, int chave);


//Somente os seguintes caracteres são considerados
//como separadores, respectivamente: todos, de frase e de palavra.
//Sendo assim, frases são consideradas todo conjunto de caracteres
//separado por algum dos caracteres em SEPARADORES_FRASE. Palavras
//são consideradas todo conjunto de caracteres separado por algum dos
//caracteres em SEPARADORES.
char SEPARADORES[]         = " \n\r\t.,:;\"!?-()'";
char SEPARADORES_FRASE[]   = "\n\r\t.!?";
char SEPARADORES_PALAVRA[] = " ,:;\"-()'";


int main(int argc, char* argv[])
{
   struct timeval ti, tf;
   long int sec, usec;
   
   //Início da contagem de tempo
   gettimeofday(&ti, NULL);


   int rank, size, slaves;       //Variáveis relevantes ao MPI
   
   int mode;                     //Modo de execução: 1 para o texto menor,
                                 //2 para o maior
   
   int *soma_ascii;              //Vetor para guardar as somas dos códigos
                                 //ASCII dos palíndromos
   
   int max_ascii = 0;            //Maior soma de códigos ASCII das palavras
   int i, j, tag = 1;
   int num_palindromos;
   char *text, *palindromos;
	MPI_Request *handle;
   StrMap *sm;                   //Tabela hash para verificação de palavras
                                 //repetidas
   
   //Inicializa MPI e variáveis relevantes à execução de todo o programa
   MPI_Init(&argc, &argv);
   MPI_Comm_rank (MPI_COMM_WORLD, &rank);
   MPI_Comm_size (MPI_COMM_WORLD, &size); 
   slaves = size - 1;
   handle = (MPI_Request*) allocate(slaves * sizeof(MPI_Request));
   mode = atoi(argv[1]);
   
   /* Nó Mestre */
   if(rank == 0)
   {
      FILE *fp;
      int file_size, diff;
      int *chunk_size, chunk_address;
      int **size_buffer;
      char **palindromos_unicos;
      int partial_size, total_size;
      int *primos, num_primos;
      int **crivos;
      
      //Determina o tamanho do arquivo
      fp = fopen(argv[2], "rb");
      fseek(fp, 0L, SEEK_END);
      file_size = ftell(fp);
      rewind(fp);
      
      //Lê o texto em memória como uma única string
      text = (char*) allocate((file_size + 1) * sizeof(char));
      if(fread(text, 1, file_size, fp) != file_size)
      {
         printf("Erro na leitura do arquivo.\n");
         exit(0);
      }
      text[file_size] = '\0';

      //Determina os tamanhos dos buffers em cada nó escravo
      chunk_size = (int*) allocate(slaves * sizeof(int));
      for(i = 0; i < slaves - 1; i++)
         chunk_size[i] = file_size / slaves;
      chunk_size[slaves - 1] = file_size - (slaves - 1) * (file_size / slaves);
      
      //Correção para frases que não terminam exatamente na fronteira entre
      //a região de processamento de nós consecutivos. Aumenta o buffer do
      //anterior e diminui o do seguinte para corrigir.
      for(i = 1; i < slaves; i++)
      {
         diff = strlen(strtok(&text[i * (file_size / slaves)], SEPARADORES_FRASE)) + 1;
         chunk_size[i - 1] += diff;
         chunk_size[i] -= diff;
      }

      //Envia o tamanho dos buffers para cada nó escravo
      for(i = 1; i <= slaves; i++)
         MPI_Isend(&chunk_size[i - 1], 1, MPI_INT, i, tag, MPI_COMM_WORLD, handle);
      //Envia o conteúdo dos buffers para cada nó escravo
      for(i = 1, chunk_address = 0; i <= slaves; i++)
      {
         MPI_Isend(&text[chunk_address], chunk_size[i - 1], MPI_CHAR, i, tag, MPI_COMM_WORLD, handle);
         chunk_address += chunk_size[i - 1];
      }
      
      //Aloca memória para receber o número de palíndromos e a quantidade de
      //memória necessária para alocá-los
      size_buffer = (int**) allocate(slaves * sizeof(int));
       
      //Recebe os dados sobre os palíndromos de cada nó escravo
      for(i = 1; i <= slaves; i++)
      {
         size_buffer[i - 1] = (int*) allocate(2 * sizeof(int));
         MPI_Irecv(size_buffer[i - 1], 2, MPI_INT, i, tag, MPI_COMM_WORLD, &handle[i - 1]);
      }
      //Espera pelo recebimento
      check_status(MPI_Waitall(slaves, handle, MPI_STATUS_IGNORE));      
      
      //Soma o total de palíndromos e a memória necessária para alocação de cada
      //um dos escravos
      for(i = 1, num_palindromos = 0, total_size = 0; i <= slaves; i++)
      {
         num_palindromos += size_buffer[i - 1][0];
         total_size += size_buffer[i - 1][1];
      }
      //Aloca memória para recebê-los
      palindromos_unicos = (char**) allocate(num_palindromos * sizeof(char*));
      if(mode == 2)
         soma_ascii = (int*) allocate(num_palindromos * sizeof(int));
      
      //Recebe os palíndromos detectados em cada escravo
      for(i = 1, partial_size = 0; i <= slaves; i++)
      {
         MPI_Irecv(&text[partial_size], size_buffer[i - 1][1], MPI_CHAR, i, tag, MPI_COMM_WORLD, &handle[i - 1]);
         partial_size += size_buffer[i - 1][1];
      }
      //Espera por todos os escravos
      check_status(MPI_Waitall(slaves, handle, MPI_STATUS_IGNORE));
      
      if(mode == 2)
      {
         //Recebe as somas dos códigos ASCII em cada escravo
         for(i = 1, partial_size = 0; i <= slaves; i++)
         {
            MPI_Irecv(&soma_ascii[partial_size], size_buffer[i - 1][0], MPI_INT, i, tag, MPI_COMM_WORLD, &handle[i - 1]);
            partial_size += size_buffer[i - 1][0];
         }
         //Espera por todos os escravos
         check_status(MPI_Waitall(slaves, handle, MPI_STATUS_IGNORE));
      }
      
      //Cria uma tabela hash
      sm = sm_new(num_palindromos);
      
      //Limpa ocorrências de palíndromos repetidos (encontrados por mais de um
      //escravo
      for(i = 0, j = 0, partial_size = 0; partial_size < total_size; i++)
      {
         if(!sm_exists(sm, &text[partial_size]))
         {
            palindromos_unicos[i] = &text[partial_size];
            sm_put(sm, palindromos_unicos[i], "");
            
            if(mode == 2)
            {
               soma_ascii[i] = soma_ascii[i + j];
               if(max_ascii < soma_ascii[i])
                  max_ascii = soma_ascii[i];
            }
         }
         else
         {
            i--;
            j++;
         }
       
         partial_size += strlen(&text[partial_size]) + 1;
      }
      num_palindromos -= j;
        
      printf("Palindromos:\n\n");
      for(i = 0; i < num_palindromos; i++)  
         printf("%d: %s\n", i + 1, palindromos_unicos[i]);
      
      
      if(mode == 2)
      {
         //Envia o valor máximo das somas ASCII (necessária para o algoritmo do
         //crivo de Erastótenes
         for(i = 1; i <= slaves; i++)
            MPI_Isend(&max_ascii, 1, MPI_INT, i, tag, MPI_COMM_WORLD, &handle[i - 1]);

         //Aloca memória para o recebimento dos crivos parciais
         crivos = (int**) allocate(slaves * sizeof(int*));
         for(i = 0; i < slaves; i++)
            crivos[i] = allocate((max_ascii + 1) * sizeof(int));
            
         //Recebe os crivos parciais de cada escravo
         for(i = 1; i <= slaves; i++)
            MPI_Irecv(crivos[i - 1], max_ascii, MPI_INT, i, tag, MPI_COMM_WORLD, &handle[i - 1]);
         
         //Espera todos os escravos
         check_status(MPI_Waitall(slaves, handle, MPI_STATUS_IGNORE));
         
         //Une todos os crivos parciais
         for(i = 2, num_primos = 0; i <= max_ascii; i++)
         {
            for(j = 1; j < slaves; j++)
               crivos[0][i] *= crivos[j][i];
            if(crivos[0][i])
               num_primos++;
         }
         
         //Cria um vetor com todos os primos do intervalo
         primos = allocate(num_primos * sizeof(int));
         for(i = 2, j = 0; j < num_primos; i++)
            if(crivos[0][i])
               primos[j++] = i; 
         
         printf("\nSomas ASCII primas:\n\n");
         for(i = 0; i < num_palindromos; i++)
            if(busca_binaria(primos, num_primos, soma_ascii[i]))
               printf("%d: %d\n", i + 1, soma_ascii[i]);
      }
   }
   /* Nós Escravos */
   else
   {
      int text_size, palindromos_size;
      int num_palavras, num_frases;
      int size_buffer[2];
      char *text_buffer, **palavras, **frases;
      char buffer[2046], *aux;
      int *crivo;
      
      //Recebe a quantidade de memória necessária para alocar o texto
      MPI_Irecv(&text_size, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, handle);
      check_status(MPI_Wait(handle, MPI_STATUS_IGNORE));
      
      //Aloca memória e recebe o texto do mestre
      text_buffer = (char*) allocate((text_size + 1) * sizeof(char));
      MPI_Irecv(text_buffer, text_size, MPI_CHAR, 0, tag, MPI_COMM_WORLD, handle);
      text_buffer[text_size] = '\0';
      text = (char*) allocate((text_size + 1) * sizeof(char));
      check_status(MPI_Wait(handle, MPI_STATUS_IGNORE));
      
      //Converte o texto para lowercase
      for(i = 0; i < text_size; i++)
         text_buffer[i] = tolower(text_buffer[i]);
      //Copia o buffer para um outro (que será modificado no processo)
      strcpy(text, text_buffer);

         
      palavras = (char**) allocate(text_size * sizeof(char*));
      palindromos = (char*) allocate(text_size * sizeof(char));
      
      //Guarda as posições de cada palavra ocorrente no texto
      palavras[0] = strtok(text, SEPARADORES);
      for(i = 0; palavras[i] != NULL; )
         palavras[++i] = strtok(NULL, SEPARADORES);
      num_palavras = i;
      soma_ascii = (int*) allocate(num_palavras * sizeof(int));
      
      //Verifica cada palavra para a ocorrência de palíndromos
      sm = sm_new(num_palavras);
      for(i = 0, palindromos_size = 0, num_palindromos = 0; i < num_palavras; i++)
         if(!sm_exists(sm, palavras[i]) && palindromo(palavras[i]))
         {
            sm_put(sm, palavras[i], "");
            strcpy(&palindromos[palindromos_size], palavras[i]);
            palindromos_size += strlen(palavras[i]) + 1;

            if(mode == 2)
               soma_ascii[num_palindromos] = word_to_ascii(palavras[i]);
            num_palindromos++;
         }

      //Repete o processo, porém para frases em vez de palavras
      if(mode == 1)
      {
         strcpy(text, text_buffer);
         frases = palavras;

         frases[0] = strtok(text, SEPARADORES_FRASE);
         for(i = 0; frases[i] != NULL; )
            frases[++i] = strtok(NULL, SEPARADORES_FRASE);
         num_frases = i;

         for(i = 0; i < num_frases; i++)
         {
            aux = strtok(frases[i], SEPARADORES_PALAVRA);
            buffer[0] = '\0';
            while(aux != NULL)
            {
               strcat(buffer, aux);
               aux = strtok(NULL, SEPARADORES_PALAVRA);
            }
            if(palindromo(buffer) && !sm_exists(sm, buffer))
            {
               sm_put(sm, buffer, "");
               strcpy(&palindromos[palindromos_size], buffer);
               palindromos_size += strlen(buffer) + 1;
               num_palindromos++;
            }
         }
      }
      
      size_buffer[0] = num_palindromos;
      size_buffer[1] = palindromos_size;

      //Envia para o mestre o número de palíndromos encontrados e a memória
      //necessária para alocá-los
      MPI_Isend(size_buffer, 2, MPI_INT, 0, tag, MPI_COMM_WORLD, &handle[0]);
      MPI_Isend(palindromos, palindromos_size, MPI_CHAR, 0, tag, MPI_COMM_WORLD, &handle[1]);
      
      if(mode == 2)
      {
         //Envia o vetor de somas ASCII para o mestre
         MPI_Isend(soma_ascii, num_palindromos, MPI_INT, 0, tag, MPI_COMM_WORLD, &handle[2]);
         //Recebe do mestre o maior valor de somas ASCII
         MPI_Irecv(&max_ascii, 1, MPI_INT, 0, tag, MPI_COMM_WORLD, &handle[3]);
         //Aguarda o recebimento
         check_status(MPI_Wait(&handle[3], MPI_STATUS_IGNORE));
         
         //Executa a seção do algoritmo do crivo de Erastótenes
         erastotenes(&crivo, max_ascii, rank, slaves); 
         //Envia o crivo parcial obtido para o mestre
         MPI_Isend(crivo, max_ascii, MPI_INT, 0, tag, MPI_COMM_WORLD, handle);
      }   
   }
   
   MPI_Finalize();

   
   if(rank == 0)
   {
      printf("\n");
      //Término da contagem de tempo
      gettimeofday(&tf, NULL);
      sec = tf.tv_sec - ti.tv_sec;
      if(tf.tv_usec < ti.tv_usec)
         sec--;
      usec = (tf.tv_usec - ti.tv_usec + 1000000) % 1000000;
      printf("Tempo decorrido: %ld.%06ld s.\n", sec, usec);
   }
   return 0;
}


//Aloca memoria, finaliza o programa em caso de erro
void* allocate(int bytes)
{
   void *ptr;
   
   ptr = malloc(bytes);
   if(ptr == NULL)
   {
      printf("Erro na alocação de memória.\n");
      exit(0);
   }
   
   return ptr;
}

//Verifica resultado de retorno de função MPI
void check_status(int status)
{
   if(status != MPI_SUCCESS)
   {
      printf("Erro na comunicação MPI.\n");
      exit(0);
   }
}
   
   

//Verifica se a palavra é palíndromo 
int palindromo(char* palavra)
{
   int i, len;
   
   len = strlen(palavra);
   
   if(len < 2)
      return 0;
   for(i = 0; i < len/2; i++)
      if(palavra[i] != palavra[len - i - 1])
         return 0;
         
   return 1;
}

//Retorna a soma dos códigos ASCII da palavra
int word_to_ascii(char* palavra)
{
   int i, soma;
   
   soma = 0;
   for(i = 0; palavra[i] != '\0'; i++)
      soma += (int) palavra[i];
   
   return soma;
}

//Algoritmo do crivo de Erastótenes (modificado para execução paralela)
void erastotenes(int** primos, int max_primo, int rank, int slaves)
{
   int i, j, start, end;
   int* crivo;
   
   crivo = (int*) allocate((max_primo + 1) * sizeof(int));
   for(i = 0; i <= max_primo; i++)
      crivo[i] = 1;

   i = (int) sqrt(max_primo) + 1;
   start = (rank - 1) * (i / slaves);
   end = rank * (i / slaves);
   if(rank == 1)
      start = 2;
   if(rank == slaves)
      end = i;
      
   for(i = start; i < end; i++)
         if(crivo[i])
            for(j = 2 * i; j <= max_primo; j += i)
               crivo[j] = 0;

   *primos = crivo;   
   return;
}

//Busca binária (utilizada na verificação de se um número é primo)
int busca_binaria(int* vetor, int tamanho, int chave)
{
   int idmin, idmax, idmed, salto;
   
   idmin = 0;
   idmax = tamanho - 1;
   
   while(idmin != idmax)
   {
      idmed = (idmin + idmax) / 2;
      
      if(idmed == idmin || idmed == idmax)
         if(vetor[idmin] == chave || vetor[idmax] == chave)
            return 1;
         else
            return 0;
      
      if(chave > vetor[idmed])
         idmin = idmed;
      else if(chave < vetor[idmed])
            idmax = idmed;
           else
            return 1;
   }
   
   return 0;
}
